We introduce a new network statistic that measures diverse structuralproperties at the micro-, meso-, and macroscopic scales, while still being easyto compute and easy to interpret at a glance. Our statistic, the onionspectrum, is based on the onion decomposition, which refines the k-coredecomposition, a standard network fingerprinting method. The onion spectrum isexactly as easy to compute as the k-cores: It is based on the stages at whicheach vertex gets removed from a graph in the standard algorithm for computingthe k-cores. But the onion spectrum reveals much more information about anetwork, and at multiple scales; for example, it can be used to quantify nodeheterogeneity, degree correlations, centrality, and tree- or lattice-likenessof the whole network as well as of each k-core. Furthermore, unlike the k-coredecomposition, the combined degree-onion spectrum immediately gives a clearlocal picture of the network around each node which allows the detection ofinteresting subgraphs whose topological structure differs from the globalnetwork organization. This local description can also be leveraged to easilygenerate samples from the ensemble of networks with a given joint degree-oniondistribution. We demonstrate the utility of the onion spectrum forunderstanding both static and dynamic properties on several standard graphmodels and on many real-world networks.
展开▼
